package LeetCode;

import java.util.Arrays;
import java.util.jar.JarEntry;

/**
 * @Author: Dijah
 * @Date: 2023/3/20 10:26
 * @Desc: 最小路径和
 * https://leetcode.cn/problems/minimum-path-sum/
 */
public class code64_minPathSum {

    //使用备忘录和dp的方式
    static int[][] memo;

    private static int minPathSum(int[][] grid){
        int m = grid.length;
        int n = grid[0].length;
        //构造备忘录
        memo = new int[m][n];
        for (int[] row : memo) {
            //初始化
            Arrays.fill(row,-1);
        }
        return dp(grid,m-1,n-1);
    }

    private static int dp(int[][] grid, int i, int j) {
        // base case
        if (i == 0 && j == 0) {
            return grid[0][0];
        }
        if (i < 0 || j < 0) {
            return Integer.MAX_VALUE;
        }
        //避免重复计算
        if(memo[i][j] != -1){
            //说明没有计算过
            return memo[i][j];
        }
        //将计算结果放到memo
        // 将计算结果记入备忘录
        memo[i][j] = Math.min(
                dp(grid, i - 1, j),
                dp(grid, i, j - 1)
        ) + grid[i][j];
        return memo[i][j];
    }

    //这个是从顶向下
    private static int minPathSum2(int [][] grid){
        int m = grid.length;
        int n = grid[0].length;
        int [][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
        //填充第0列
        for (int i = 1; i < m; i++){
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }
        //填充第0行
        for(int j = 1; j < n; j++){
            dp[0][j] = dp[0][j-1] + grid[0][j];
        }
        //状态转移
        for(int i = 1; i < m; i++){
            for (int j = 1; j < n; j++){
                dp[i][j] = Math.min(
                        dp[i-1][j],
                        dp[i][j-1]
                ) + grid[i][j];
            }
        }
        return dp[m-1][n-1];
    }

    public static void main(String[] args) {
        int [][] grid = {{1,3,1},{1,5,1},{4,2,1}};
        int i = minPathSum2(grid);
        System.out.println(i);
        int i1 = minPathSum(grid);
        System.out.println(i1);
    }
}
